package com.ztom.v2;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author ZhangTao
 */
public class Code35LRUCache {

    static class Node {
        public int key;
        public int val;
        public Node pre;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    static class LRUCache {
        private final Node dummyHead;
        private final Node dummyTail;
        private final Map<Integer, Node> cache;
        private final int capacity;
        private int size;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.dummyHead = new Node(-1, -1);
            this.dummyTail = new Node(-1, -1);
            this.cache = new HashMap<>(capacity);
            this.size = 0;
            this.dummyHead.next = this.dummyTail;
            this.dummyTail.pre = this.dummyHead;
        }

        public int get(int key) {
            if (cache.containsKey(key)) {
                Node node = cache.get(key);
                // 移动到最前面
                delNode(node);
                insertHead(node);
                return node.val;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (cache.containsKey(key)) {
                // 删除旧节点
                delNode(cache.get(key));
            } else if (size >= capacity) {
                // 删除尾节点
                delNode(dummyTail.pre);
            }
            // 新建结点, 插入到头部
            insertHead(new Node(key, value));
        }

        private void insertHead(Node newHead) {
            // 旧头
            Node oldHead = dummyHead.next;
            oldHead.pre = newHead;
            // 新头
            newHead.pre = dummyHead;
            newHead.next = oldHead;

            dummyHead.next = newHead;
            cache.put(newHead.key, newHead);
            size++;
        }

        private void delNode(Node node) {
            if (node == dummyHead || node == dummyTail) {
                // 哨兵节点, 不删除
                return;
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
            cache.remove(node.key);
            size--;

            node.pre = null;
            node.next = null;
            node = null;
        }
    }

    static class LRUCache1 {

        private final int capacity;
        private final LinkedHashMap<Integer, Integer> data;

        public LRUCache1(int capacity) {
            this.capacity = capacity;
            this.data = new LinkedHashMap<>(capacity);
        }

        public int get(int key) {
            Integer res = data.getOrDefault(key, -1);
            // 移到最后
            if (res != -1) {
                this.put(key, res);
            }
            return res;
        }

        public void put(int key, int value) {
            if (data.containsKey(key)) {
                data.remove(key);
            } else if (data.size() >= capacity) {
                data.remove(data.keySet().iterator().next());
            }
            data.put(key, value);
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}
